package graph;

import java.util.Iterator;

/**
 *
 * @author Roberto Maestre Martínez <roberto.maestre AT cchs.csic.es>
 */
public class DirectGraph extends Graph {

    
    private PathCost aux,result;
    private int auxCost;


    public void addEdge(int x, int y, int weigth) throws Exception {
        m[x][y]=weigth;
    }

    
    public String toGraphviz() throws Exception {
        String string="digraph Grafo{ ";
       for (int i=1;i<N;i++)
           for (int j=1;j<N;j++)
               if (m[i][j]!=INF)
                    string+=i+"->"+j+" [label=\""+this.getEdgeWeight(i, j)+"\"];";
       string+="}";
       return string;
    }


    public PathCost getPathAndCostBetweenNodes(int start, int end) {
        aux = new PathCost();
        aux.getPath().add(start);
        result = null;
        auxCost=Integer.MAX_VALUE;
        visits = new boolean[N];
        for (int i=1;i<N;i++) visits[i]=false;
        visits[start]=true;
        this.btGetPathAndCostBetweenNodes(start, end, start);
        return result;
    }



    /**
    * Add edge between tow nodes of the graph with weight
    * This method use backtracking
     *
    * @param start start node
    * @param end end node
    * @param node exploration node
    */
    private void btGetPathAndCostBetweenNodes(int start, int end, int node){
        for(int a=1;a<N;a++) {
            if (m[node][a]!=INF && a!=node && !visits[a]) {
                visits[a]=true;
                aux.setCost(aux.getCost()+m[node][a]);
                aux.getPath().add(a);
                if (a==end && aux.getCost()<auxCost) {
                    result = new PathCost();
                    Iterator i = aux.getPath().iterator();
                    while (i.hasNext()) result.getPath().add((Integer) i.next());
                    result.setCost(aux.getCost());
                    auxCost = aux.getCost();
                } 
                btGetPathAndCostBetweenNodes(start,end,a);
                visits[a]=false;
                aux.setCost(aux.getCost()-m[node][a]);
                aux.getPath().remove(aux.getPath().size()-1);
            }
        }
    }

}
